package com.demo.algorithm;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 */
public class 两数之和 {

	/**
	 * 方式一：暴力实现
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public int[] twoSum(int[] nums, int target) {
		int[] index = new int[2];
		for (int i = 0; i < nums.length; i++) {
			for (int j = nums.length - 1; j > i; j--) {
				if (nums[i] + nums[j] == target) {
					index[0] = i;
					index[1] = j;
					return index;
				}
			}
		}
		return index;
	}

	/**
	 * 方式二：
	 * 1. 用字典(哈希表)存储每个数对应的索引
	 * 2. 当target - 当前数 在 字典(哈希表) 中存在时，说明已存储的数和当前数相加可以达到目标 target
	 * 3. 返回对应的索引 [hashmap[target - num], i]
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public int[] twoSum1(int[] nums, int target) {

		int[] index = new int[2];

		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(nums[i])) {
				index[0] = map.get(nums[i]);
				index[1] = i;
				return index;
			}
			map.put(target - nums[i], i);
		}
		return index;
	}

	@Test
	public void testTwoSum1() {
		int[] nums = {3, 2, 4, 1, 2};
		int target = 6;
		int[] result = twoSum(nums, target);
		for (final int i : result) {
			System.out.println(i);
		}
	}
}
